/*
 * 教材中的示例程序之完整版.
 * 书名：《编译原理基础》
 * 版次：第三版
 * 作者：王献青，张立勇，张淑平，刘坚
 * 出版社：西安电子科技大学出版社
 * 程序完成时间：2025.03
 */

//
// 文件内容：文法 G3.9" 所描述语言的词法分析器实现
//
// 函数 nextToken() 可被看做是词法分析其的关键API操作
//

// 这个词法分析器与 chap02/lexer.c 的不同之处在于:
// 1. 被分析的语言(词法规则)不同；
// 2. 这是一个“表驱动的"识别器(示例)，而 chap02 中仅给出了直接编码的、手工编码的示例。
// 3. 每次识别完一个单词后，单词文本的范围表示方式不一样：
//    这个实现中，单词范围是 [lexeme_begin, forward), 而 chap02 的
//       实现中，单词范围是 [lexeme_begin, forward]。


#include <string.h>

#include "lexer.h"

// 简易的输入缓冲区(见教材2.5.1节)，本程序不考虑其更新

#define BUFFER_SIZE 2048
static char   buffer[BUFFER_SIZE +1];
static char * lexeme_begin;    // 指向单词的第一个字符
static char * forward;  // 指向当前字符，用于向前扫描
                 // 当识别到一个单词后，它指向该单词之后的"下一字符"

#define MY_EOF_       '\0'     //表示输入结束的特殊符号的实现
#define IS_EOF(c)     ((c)==MY_EOF_)


// globToken 是存储下一记号的全局量.
// ~~~~~~  特别提示 ~~~~~~
// 使用一个全局记号对象，仅限于满足下述约束的应用场景：
// 1. 不需要建立记号流对象，
// 2. 词法分析器更新该对象，语法分析器读取该对象，
// 3. 语法分析、语义分析过程中，不对记号对象进行复制，
// 4. 用于 LL(1) 语法分析器。可能不能适用于 SLR(1), LR(1) 等分析方法。
//
t_token  globToken;     // 下一记号


//设置待分析的输入，将其复制到内部缓冲区
void set_lexer_input(const char * input) {
    strncpy(buffer, input, BUFFER_SIZE);
    buffer[BUFFER_SIZE] = '\0';
    lexeme_begin = buffer;
    forward = buffer;

    globToken.kind = ERROR;
    globToken.line = 1;
    globToken.column = 1;
}

static TokenKind recognize_word();
static void skip_whitespaces();

/*
 * 获取下一记号的识别函数.
 *
 * 返回记号类别，所得记号的全部信息存储到全局量 globToken。
 */
TokenKind  nextToken() {
    if (EOFS == globToken.kind) // 防止遇到 EOF 后，当前函数还被反复调用
        return EOFS;

    globToken.column += (int)(forward - lexeme_begin);
    globToken.kind = ERROR;
    memset(globToken.word, 0, sizeof(globToken.word));

    //  因为图2.26给出的DFA并未考虑空白字符，所以必须在
    //  这里处理
    skip_whitespaces();      // 跳过单词前面可能存在的空白字符
    if ( IS_EOF(*forward) ) {
        return globToken.kind = EOFS;
    }

    lexeme_begin = forward;  // 两个指针：指向下一单词的第一个字符
    globToken.kind = recognize_word();  // 单词识别

    //遇到无效字符，令 forward 指向下一字符，否则无限循环了
    if(ERROR == globToken.kind)
        ++forward;

    // 将单词复制到记号对象中，但最多仅保存 WORDLEN_MAX 个字符
    int L = 0;
    for(const char * p = lexeme_begin ; p < forward ; ++p) {
        globToken.word[L++] = *p;
        if ( IS_EOF(*p) || L == WORDLEN_MAX ) break;
    }
    globToken.word[L] = '\0';

    return globToken.kind;
}


// 跳过空白字符，此处仅考虑三个空白字符
static void skip_whitespaces() {
    for(char c;  ; ++forward) {
        c = *forward;
        switch(c) {
            case '\n' :  // 思考：如何处理 '\r' 字符？
                globToken.line += 1; globToken.column = 1;
                break;
            case ' ' :  case '\t':
                globToken.column += 1;
                break;
            default:
                return;
        }
    }
}


// 将记号种类编码翻译为文字，便于阅读程序输出.
//  ** 这是一个低效实现。当记号种类较多时，
//     最好使用哈希表或其他更高效的数据结构和查找算法。
const char * lookup_kindname(TokenKind kind) {
    switch(kind) {
        case EOFS:  return  "EOF";
        case ERROR: return  "ERROR";
        case ID:    return  "ID";
        case NUM:   return  "NUM";
        case LP:    return  "LP";
        case RP:    return  "RP";
        case PLUS:  return  "PLUS";
        case MINUS: return  "MINUS";
        case MUL:   return  "MUL";
        case DIV:   return  "DIV";
        case MOD:   return  "MOD";
        case SEMICO:    return  "SEMI";
        default:    return "UNKNOWN";
    }
}


//==============================================================
//
//  下面是表驱动的单词识别函数, 并演示了压缩表的一种形式
//

#define  START_STATE   0          // DFA的初态
static int dfa_move(int, char);
static TokenKind  dfa_is_final(int);

/*
 * 表驱动型单词识别器的主控函数（模拟DFA算法的实现），
 * 识别下一单词，返回其记号种类.
 *
 * 调用前，调用者应令
 *   lexeme_begin = forward = 指向下一单词的第一个字符，
 * 该函数返回时，
 * 所得单词是在范围 [lexeme_begin, forward) 内的字符序列。
 * 若返回 ERROR(发现一个错误)，则 forward 恰好指向这次发现的无效字符。
 */
static TokenKind recognize_word() {
    int state = START_STATE;  // 当前状态，初值为DFA的初态

    for( ; ! IS_EOF(*forward); ++forward) {  // 扫描+状态转移
        char c = *forward;
        int nextState = dfa_move(state, c);
        if( nextState < 0)
            break;
        state = nextState;
    }

    // 是否到达终态(接受)，若是，还需确定记号类别
    //   提示： 模拟DFA算法仅仅回答“是否接受输入”。
    TokenKind kind = dfa_is_final(state);
    if (ID == kind) {  // 处理关键字
        // 因为下文的“表驱动的识别器实现”将关键字和 id 均识别为 ID，所以
        // 这里需要辨别关键字。
        //
        // 因为当前分析的语言只有一个关键字，所以就简单比较字符串即可。
        // 若关键字较多，往往需要设置一个关键字表，
        // 以提供处理效率.
        if(strncmp("mod", lexeme_begin, 3) == 0)
            kind = MOD;
    }

    return kind;
}


//----------------------- TRANSITIONS ---------------------------
//
// 下面是采用稀疏数组+压缩表表示的转移集合 以及 转移查询函数
//


// 三个字符类
#define  CLASS_SINGLE  0   // 单一字符类
#define  CLASS_LETTER  1   // 字母字符类， [a-zA-Z_]
#define  CLASS_DIGIT   2   // 数字字符类， [0-9]
typedef int t_char_class;


#define IS_LETTER(c)  (('A'<=(c) && (c)<='Z') || ('a'<=(c) && (c)<='z') || (c)=='_')
#define IS_DIGIT(c)   ('0'<=(c) && (c)<='9')

// 确定字符 c 的字符类
static t_char_class  get_char_class(char c) {
    if ( IS_LETTER(c) )
        return CLASS_LETTER;
    if ( IS_DIGIT(c) )
        return CLASS_DIGIT;
    return CLASS_SINGLE;
}

// 将字符、字符类合成为一个字，作为转移的标记
#define  MK_LABEL(c, class)     ((class) << 16 | ((c) & 0xffff))
#define  CLASS_LABEL(g)         MK_LABEL(0, g)
#define  CHAR_LABEL(c)          c   // MK_LABEL(c, CLASS_SINGLE)

// 判断字符是否在转移的标记中
#define  IN_LABEL_CLASS(label, class)   (((label) >> 16) & (class))
#define  IN_LABEL_CHAR(label, c)        ((label) == (c))
#define  IN_LABEL(label, c, class)  (class == CLASS_SINGLE) ? \
        IN_LABEL_CHAR(label,c) : \
        IN_LABEL_CLASS(label, class)

// 表示一条状态转移的数据结构，这里使用按字符分类的压缩表形式
typedef struct  transition {
    int  state_from;    // 转移的源状态
    int  state_to;      // 转移的目标状态
    int  label;         // 转移的标记，一个字符或字符类
} t_transition;

// 全体状态转移的数据表示, 这里表示为一个 稀疏数组+压缩表。
// NOTICE: 排序规则是 先按 .from 升序排，再按 .to 升序排。
static t_transition  transitions[] = {
    {0, 1, CHAR_LABEL('+') },
    {0, 2, CHAR_LABEL('-') },
    {0, 3, CHAR_LABEL('*') },
    {0, 4, CHAR_LABEL('/') },
    {0, 5, CHAR_LABEL('(') },
    {0, 6, CHAR_LABEL(')') },
    {0, 7, CHAR_LABEL(';') },
    {0, 8, CLASS_LABEL(CLASS_LETTER) },
    {0, 9, CLASS_LABEL(CLASS_DIGIT) },
    {8, 8, CLASS_LABEL(CLASS_LETTER | CLASS_DIGIT) },
    {9, 9, CLASS_LABEL(CLASS_DIGIT) }
};
static size_t  N_TRANS = sizeof(transitions)/sizeof(transitions[0]);

// get the next-state of move(state, c)
static int dfa_move(int state, char c) {
    t_char_class charClass = get_char_class(c);
    for (size_t i = 0; i < N_TRANS; ++i) {
        if (transitions[i].state_from == state ) {
            if (IN_LABEL(transitions[i].label, c, charClass))
                return transitions[i].state_to;
            continue;
        }
        if (transitions[i].state_from < state)
            continue;
        if (transitions[i].state_from > state)
            break;
    }

    return -1;  // no transition for move(state, c)
}


//-----------------------  FINAL STATES -------------------------
//
//  下面示例了表示 "终态->记号类别“ 映射关系的 两种方式
//
// 方式1. 二元组集合，每个二元组为 <终态,  对应的记号类别>
//   仅当定义宏 FINAL_IN_PAIR，且其值为1时被使用。
//   #define FINAL_IN_PAIR 1
//
// 方式2. 整数数组，元素的下标即状态.
//   当未定义宏 FINAL_IN_PAIR，或其值非1时被使用。
//   #undef FINAL_IN_PAIR
//

#if  defined(FINAL_IN_PAIR) && FINAL_IN_PAIR == 1

// 定义 一个终态到记号类别的映射关系的二元组
typedef struct  final_kind_pair {
    int  state;
    TokenKind  kind;
} t_final_kind_pair;

// 从终态到记号类别映射关系的数据表示方式 1： 二元组集合.
// NOTICE: 这里仅需记录终态们对应的记号类别。
static t_final_kind_pair  finalStates[] = {
        {1, PLUS},
        {2, MINUS},
        {3, MUL},
        {4, DIV},
        {5, LP},
        {6, RP},
        {7, SEMICO},
        {8, ID},
        {9, NUM}
};
static size_t  N_FINALS = sizeof(finalStates)/sizeof(finalStates[0]);

//确定当前状态是否为终态，若是则返回对应的记号类别，否则返回 ERROR
static TokenKind  dfa_final(int state) {
    for(size_t i=0; i<N_FINALS; ++i) {
        if(state == finalStates[i].state)
            return finalStates[i].kind;
    }
    return ERROR;
}

#else  // #if defined(FINAL_IN_PAIR) && FINAL_IN_PAIR == 1

// 从终态到记号类别映射关系的数据表示方式 2：整数数组，状态为下标。
// NOTICE: 这里需要定义DFA的每个状态对应的记号类别，其中
//      非终态对应到 ERROR 上。
static TokenKind  state_kind_table[] = {
        ERROR,
        PLUS,
        MINUS,
        MUL,
        DIV,
        LP,
        RP,
        SEMICO,
        ID,
        NUM
};
static size_t  N_FINALS = sizeof(state_kind_table)/sizeof(state_kind_table[0]);

//确定当前状态是否为终态，若是则返回对应的记号类别，否则返回 ERROR
static TokenKind  dfa_is_final(int state) {
    if(state >= 0 && state < N_FINALS)
        return state_kind_table[state];
    else
        return ERROR;
}

#endif  // #if defined(FINAL_IN_PAIR) && FINAL_IN_PAIR == 1
